package com.my.test.permutation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permutation {
	
	/**
	 * Precondition is <code>char[] d</code> must be an ordered array.
	 * 
	 * @param d A char array which is already sorted.
	 * @return All possible permutations.
	 */
	public static void doPermutation(char[] d) {
		if(d == null || d.length == 0) {
			return;
		} 
		recurPermutation(d, d.length);
	}
	
	public static void recurPermutation(char[] d, int len) {
		if(d == null || d.length == 0)
			throw new IllegalArgumentException("char[] d must not be null or empty. ");
		int hIdx = d.length - len;
		if(hIdx == d.length) 
			return;
		int rotateStart = hIdx + 1;
		List<char[]> rotated = rotate(d, hIdx, rotateStart);
		for(char[] ch : rotated) {
			recurPermutation(ch, len--);
		}
	}
	
	private static List<char[]> rotate(char[] d, int startIdx, int endIdx) {
		List<char[]> buf = new ArrayList<>();
		int rotateStart = startIdx + 1;
		while(rotateStart <= d.length - 1) {
			swap(d, startIdx++, rotateStart++);
			buf.add(Arrays.copyOf(d, d.length));
			dispalyData(d);
			recurPermutation(d, startIdx);
		}
		return buf;
	}
	
	private static void dispalyData(char[] d) {
		for(char c : d) {
			System.out.print(c + " ");
		}
	}
	
	private static void swap(char[] d, int first, int second) {
		if(second <= first) 
			return;
		d[first] ^= d[second];
		d[second] ^= d[first];
		d[first] ^= d[second];
	}

	
	private static void reverse(char[] d, int start, int end) {
		if(end <= start) return;
		for(int i=start, j=end; i<j; i++, j--) {
			swap(d, i, j);
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
